package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/study/live/719/1/2?autoplay=1">
 * 第2节 随堂练习-城市路径</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定一个路径数组paths，表示一张图。
 * paths[i]==j代表城市i连向城市j，如果paths[i]==i表示i城市是首都，一张图里只会有一个首都，不会有分图且图中除了首都指向自己之外不会有环；
 * 例如：paths={9,1,4,9,0,4,8,9,0,1} 由这个数组表示的图如下图所示。
 * 城市1是首都所以距离为0；离首都距离为1的城市只有城市9；离首都距离为2的城市有城市0，3，7；离首都距离为3的城市有城市4，8；离首都距离为4的城市有城市2，5，6； 所以，距离为0的城市有1座；距离为1的城市有1座；距离为2的城市有3座；距离为3的城市有2座；距离为4的城市有3座；那么统计数组为numArr={1,1,3,2,3,0,0,0,0,0}，numArr[i]==j代表距离为i的城市有j座； 要求实现一个void类型的函数，输入一个路径数组paths，直接在原数组上调整，使之变为numArr数组。 paths={9,1,4,9,0,4,8,9,0,1}，函数处理后，paths={1,1,3,2,3,0,0,0,0,0}。 要求：如果paths长度为N，时间复杂度为O(N)，额外空间复杂度为O(1)；
 * <img src="http://uploadfiles.nowcoder.com/images/20150312/60_1426131547233_1.jpg">
 *
 * @author or2
 * @date 2021年09月30日 时间: 17:46
 */
public class Advanced1$2 {
    /**
     * 将路径数组变为统计数组
     * 输入：代表一张图的数组paths
     * 将paths数组变为距离数组numArr
     */
    public void pathArrToNumArr(int[] paths) {
        /* 第一步: 计算距离 (注意表示方式) */
        int pre, next;
        for (int i = 0, len = paths.length; i < len; i++)
            if (paths[i] >= 0) {
                /* 辅助变量 */
                pre = i;
                next = paths[i];
                /* 跳过首都的处理 */
                if (next == i)
                    continue;
                /* 迭代到首都, 更新沿途值 */
                while (next != paths[next]) {
                    int cur = next;
                    next = paths[next];
                    /* 若当前值为负, 说明以及被更新 */
                    if (next < 0)
                        break;
                    paths[cur] = pre;
                    pre = cur;
                }

                /* 逆推回去, 更新成距离 (若吓一跳结点值为负, 直接复用其结果) */
                int distance = Math.min(next, 0);
                while (pre != i) {
                    next = paths[pre];
                    paths[pre] = --distance;
                    pre = next;
                }
                paths[i] = --distance;
            }
        /* 首都到自己的距离为0 */
        for (int i = 0, len = paths.length; i < len; i++)
            if (paths[i] > 0)
                paths[i] = 0;

        /* 第二步: 根据距离信息统计城市数目 */
        /* 此时, 元素值的含义再次变换, 负数表示到首都的距离, 正数表示`距离该下标值到首都`的城市个数 */
        for (int i = 0, len = paths.length; i < len; i++)
            if (paths[i] <= 0) {
                /* i 出发点 */
                next = -paths[i];
                /* 在出发点之前的数据一定被走过, 直接覆盖 */
                if (next <= i) {
                    if (paths[next] < 0) {
                        paths[next] = 1;
                    } else
                        paths[next]++;
                    continue;
                }
                /* 开始迭代更新 */
                while (next != i) {
                    pre = paths[next];
                    if (pre < 0) {
                        paths[next] = 1;
                        next = -pre;
                    } else {
                        paths[next]++;
                        break;
                    }
                }
            }

        int end = binarySearch(paths);
//        Arrays.fill(paths, end, paths.length, 0);
        for (int i = end, len = paths.length; i < len; i++)
            paths[i] = 0;
    }

    private int binarySearch(int[] arr) {
        /* [) */
        int left = 0, right = arr.length;
        int mid;
        while (left < right) {
            mid = right + left >> 1;
            if (arr[mid] <= 0) {
                if (arr[mid - 1] >= 0)
                    return mid;
                right = mid;
            } else
                left = mid + 1;
        }

        return left;
    }
}
